package _dp_base;

import java.util.Arrays;

/**
 * 377. 组合总和 Ⅳ
 */
public class No377 {
    private int[] nums;
    private int[] cache;

    /**
     * 1. 递归
     */
    public int combinationSum41(int[] nums, int target) {
        this.nums = nums;
        cache = new int[target + 1];
        Arrays.fill(cache, -1);

        return dfs(target);
    }

    private int dfs(int i) {
        if (cache[i] != -1) return cache[i];
        if (i == 0) return cache[i] = 1;
        int curLen = 0;
        for (int num : nums) {
            if (i >= num) curLen += dfs(i - num);
        }
        return cache[i] = curLen;
    }

    /**
     * 2. 迭代
     */
    public int combinationSum42(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 1; i < f.length; i++) {
            int curLen = 0;
            for (int num : nums) {
                if (i >= num) curLen += f[i - num];
            }
            f[i] = curLen;
        }
        return f[target];
    }
}
